1. Field of the Invention
The invention is in the field of computer science and specifically in the field of network communications.
2. Prior Art
The Internet is a network of computing systems configured to communicate with each other. Communication is accomplished using a system of unique numerical addresses such as Internet Protocol (IP) addresses. However, computing systems connected to the internet are also addressable using “domain names” such as www.nominum.com. When a domain name is used to specify a location on the internet, the domain name is translated (i.e., “resolved”) into the IP address of that location by the Domain Name System (DNS). The DNS also stores other types of information that may be looked up by domain name, such as information for routing electronic mail.
An Internet domain name contains a hierarchy of labels, conventionally separated by dots. For example, the domain name www.nominum.com is part of the “nominum.com” domain, which in turn is a subdomain of the “com” domain, which is a subdomain of the “root domain.” The root domain can be viewed as a parent domain of “com,” which in turn is a parent domain of “nominum.com,” etcetera. Other valid addresses defined under the nominum.com domain may include, for example, “products.nominum.com” or “sales.nominum.com.” Often a domain name is used in conjunction with directory or file information to form a Universal Resource Locator (URL) associated with a specific file (e.g., www.nominum.com/main/products.html).
Information to be looked up in the DNS is stored in servers referred to as “authoritative servers.” An authoritative server stores the information pertaining to a particular domain, exclusive of any subdomains that have been delegated to their own authoritative servers. Additionally, servers that are authoritative for a parent domain store information identifying servers authoritative for its delegated subdomains, for use in referring information requests.
When a domain name is entered at a client computer, the client computer typically queries a local “caching server” which resolves the name into an IP address or other desired DNS information on the client's behalf and then returns the information to the client. This caching server may, for example, be managed by a local internet service provider.
The caching server resolves names by querying one or more authoritative servers. For example, to resolve the name “www.nominum.com,” a typical caching server may first query one of the servers authoritative for the root domain, which responds with a “referral response” identifying the servers authoritative for the “com” domain. The caching server then queries one of the servers authoritative for the “com” domain, which responds with another referral response identifying the servers authoritative for the “nominum.com” domain. Finally, the caching server queries one of the servers authoritative for the “nominum.com” domain, which responds with an “answer response” containing the desired information regarding www.nominum.com.
The caching server also includes a cache of information previously received from authoritative servers as a result of past queries, so as to improve efficiency by avoiding repeated queries. Typically, cache data are stored in a tree structure such that navigating the cache starting from a root node yields either the desired answer or, when the answer is not present, identifies the closest parent domain for which cached information identifying its authoritative servers is present, allowing that information to serve as a starting point for the process of querying authoritative servers as described above. In a typical cache, information from both answer responses and referral responses is stored in the same tree structure. When the cache data are stored in a tree structure, a search of the cache can be accomplished in a time that grows in proportion to the number of labels in the domain name being translated.
A caching server may process thousands of queries per second and search a cache including hundreds of megabytes of data. There is, therefore, a need for systems and methods that improve the efficiency of the translation of domain names to DNS data, such as IP addresses.